# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 9_count_sort.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2022/1/20 14:03
------------------------------------------
    计数排序
"""


def count_sort(array):
    """
        计数排序
    """
    # 1.计算数组的最大值和最小值
    max_value = array[0]
    min_value = array[0]

    for i in range(1, len(array)):
        if array[i] > max_value:
            max_value = array[i]

        if array[i] < min_value:
            min_value = array[i]

    # 2.根据最大值和最小值确定统计数组的长度
    count_array = [0] * (max_value - min_value + 1)

    # 3.遍历待排序数组，填充统计数组
    for j in range(0, len(array)):
        count_array[array[j]] += 1

    # 4.遍历统计数组，输出结果
    sorted_array = []
    for k in range(0, len(count_array)):
        for _ in range(count_array[k]):
            sorted_array.append(k + min_value)

    return sorted_array


def count_sort_v2(array):
    """
        计数排序优化版
            - 对统计数组长度进行了优化；
            - 对相同数值的排名顺序进行了保留，比如单科成绩排名
    """
    # 1.计算数组的最大值和最小值，并计算出差值
    max_value = array[0]
    min_value = array[0]

    for i in range(1, len(array)):
        if array[i] > max_value:
            max_value = array[i]

        if array[i] < min_value:
            min_value = array[i]

    d = max_value - min_value

    # 2.创建统计数组并统计对应元素个数
    count_array = [0] * (d + 1)
    for i in range(0, len(array)):
        count_array[array[i] - min_value] += 1

    # 3.统计数组作变形，后边的元素值等于前边的元素值之和
    for j in range(1, len(count_array)):
        count_array[j] += count_array[j - 1]

    # 4.倒叙遍历原始数组，从统计数组找到正确的位置，输出到结果数组
    sorted_array = [0] * len(array)
    for k in range(len(array) - 1, -1, -1):
        array_cell = array[k]

        # count_array[array_cell - min_value] 得到的是从1开始序号，而索引从0开始，需要-1
        sorted_array[count_array[array_cell - min_value] - 1] = array_cell

        # 将序号减1
        count_array[array_cell - min_value] -= 1

    return sorted_array


def demo():
    my_array = [4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10]
    print(count_sort(my_array))


def demo_v2():
    my_array = [95, 94, 91, 98, 99, 90, 93, 91, 92]
    print(count_sort_v2(my_array))


if __name__ == '__main__':
    demo_v2()
